﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Diagnostics;

namespace Algorithm.Struct
{
    /*
     * 红黑树说明：红黑树是一个二叉查找树，并满足一下性质
     * 1. 每个节点或是红，或是黑
     * 2. 根节点是黑的
     * 3. 每个叶节点是黑的
     * 4. 如果一个节点是红的，则它的两个孩子就是黑的
     * 5. 对每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点
     * 
     * 黑高度定义：从某个节点x 到达一个叶子节点的路径上，黑色节点的数量，由性质5可知，黑高度是一定的。
     */
    public class RedBlackTree<T> : SearchBTree<T> where T : IComparable<T>, IEquatable<T>
    {
        public RedBlackTree(RedBlackTreeNode<T> root)
            : base(root)
        { }

        public virtual void RBInsert(RedBlackTreeNode<T> node)
        {
            node.Tree = this;
            if (null == this.Root)
            {
                node.Color = NodeColor.Black;
                this.Root = node;
            }
            else
            {
                TreeNode<T> nodeParent = null;
                var tmp = this.Root;
                while (EmptyTreeNode<T>.Instance() != tmp)
                {
                    nodeParent = tmp;
                    if (node.Data.CompareTo(tmp.Data) < 0)
                    {
                        tmp = tmp.LeftNode;
                    }
                    else
                    {
                        tmp = tmp.RightNode;
                    }
                }
                node.Parent = nodeParent;
                if (EmptyTreeNode<T>.Instance() == nodeParent)
                {
                    this.Root = node;
                }
                else if (node.Data.CompareTo(nodeParent.Data) < 0)
                {
                    nodeParent.LeftNode = node;
                }
                else
                {
                    nodeParent.RightNode = node;
                }
                node.Color = NodeColor.Red;
                RB_Insert_Fixup(node);
            }
        }

        /// <summary>
        /// 修正及调整节点 使之满足红黑树性质
        /// 该算法分为六种情况讨论，根据该节点的父节点是祖父节点的左孩子还是右孩子各三种情况（对称）
        /// 下面以左孩子情况三种情况：
        /// 1. 叔叔节点为红色：
        /// 2. 叔叔节点为黑色，插入节点为右孩子：
        /// 3. 叔叔节点为黑色，插入节点为左孩子：
        /// 
        /// 详细分析见算法导论 中文版本 280页
        /// </summary>
        /// <param name="node"></param>
        protected void RB_Insert_Fixup(RedBlackTreeNode<T> node)
        {
            var currentNode = node;
            while ((currentNode.Parent as RedBlackTreeNode<T>).Color == NodeColor.Red)
            {
                if (currentNode.Parent == currentNode.Parent.Parent.LeftNode)
                {
                    var uncle = currentNode.Parent.Parent.RightNode;
                    if ((uncle as RedBlackTreeNode<T>).Color == NodeColor.Red)
                    {
                        (currentNode.Parent as RedBlackTreeNode<T>).Color = NodeColor.Black;
                        (uncle as RedBlackTreeNode<T>).Color = NodeColor.Black;
                        (currentNode.Parent.Parent as RedBlackTreeNode<T>).Color = NodeColor.Red;
                        currentNode = currentNode.Parent.Parent as RedBlackTreeNode<T>;
                    }
                    else
                    {
                        if (currentNode == currentNode.Parent.RightNode)
                        {
                            currentNode = currentNode.Parent as RedBlackTreeNode<T>;
                            currentNode.Left_Rotate();
                        }
                        (currentNode.Parent as RedBlackTreeNode<T>).Color = NodeColor.Black;
                        (currentNode.Parent.Parent as RedBlackTreeNode<T>).Color = NodeColor.Red;
                        (currentNode.Parent.Parent as RedBlackTreeNode<T>).Right_Rotate();
                    }
                }
                else//与上面的逻辑对称
                {
                    var uncle = currentNode.Parent.Parent.LeftNode;

                    if ((uncle as RedBlackTreeNode<T>).Color == NodeColor.Red)
                    {
                        (currentNode.Parent as RedBlackTreeNode<T>).Color = NodeColor.Black;
                        (uncle as RedBlackTreeNode<T>).Color = NodeColor.Black;
                        (currentNode.Parent.Parent as RedBlackTreeNode<T>).Color = NodeColor.Red;
                        currentNode = currentNode.Parent.Parent as RedBlackTreeNode<T>;
                    }
                    else
                    {
                        if (currentNode == currentNode.Parent.LeftNode)
                        {
                            currentNode = currentNode.Parent as RedBlackTreeNode<T>;
                            currentNode.Right_Rotate();
                        }
                        (currentNode.Parent as RedBlackTreeNode<T>).Color = NodeColor.Black;
                        (currentNode.Parent.Parent as RedBlackTreeNode<T>).Color = NodeColor.Red;
                        (currentNode.Parent.Parent as RedBlackTreeNode<T>).Left_Rotate();
                    }
                }
            }
            (this.Root as RedBlackTreeNode<T>).Color = NodeColor.Black;
        }



        public virtual void RB_Delete(RedBlackTreeNode<T> node)
        {
            TreeNode<T> willDel = null;
            if (EmptyTreeNode<T>.Instance() == node.LeftNode || EmptyTreeNode<T>.Instance() == node.RightNode)
            {
                willDel = node;
            }
            else
            {
                willDel = node.GetSuccessor();
            }

            TreeNode<T> willDelChild = null;
            if (EmptyTreeNode<T>.Instance() != willDel.LeftNode)
            {
                willDelChild = willDel.LeftNode;
            }
            else
            {
                willDelChild = willDel.RightNode;
            }

            //更新原孙子节点父指针指向
            willDelChild.Parent = willDel.Parent;

            //如果被删除的是根节点
            if (EmptyTreeNode<T>.Instance() == willDel.Parent)
            {
                this.Root = willDelChild;
            }
            else if (willDel == willDel.Parent.LeftNode) //更新原祖父节点的孩子指针
            {
                willDel.Parent.LeftNode = willDelChild;
            }
            else
            {
                willDel.Parent.RightNode = willDelChild;//更新原祖父节点的孩子指针
            }

            //下面的判断说明willDel 节点为后继节点
            if (willDel != node)
            {
                node.Data = willDel.Data;
            }

            var del = willDel as RedBlackTreeNode<T>;
            if(del.Color== NodeColor.Black)
            {
                RB_Delete_Fixup(willDelChild as RedBlackTreeNode<T>);
            }
        }

        /// <summary>
        /// 分三种情况讨论：
        /// 1. 当前节点为根节点，把颜色标记为黑色
        /// 2. 当前节点为红黑节点，把颜色标记为黑色
        /// 3. 做转换和颜色修改
        /// </summary>
        /// <param name="node"></param>
        protected void RB_Delete_Fixup(RedBlackTreeNode<T> node)
        {
            var currentNode = node;
            RedBlackTreeNode<T> w = null;
            while (null != currentNode && Root != currentNode && node.Color == NodeColor.Black)
            {
                if (currentNode == currentNode.Parent.LeftNode)
                {
                    w = currentNode.Parent.RightNode as RedBlackTreeNode<T>;
                    if (w.Color == NodeColor.Red)
                    {
                        w.Color = NodeColor.Black;
                        (currentNode.Parent as RedBlackTreeNode<T>).Color = NodeColor.Red;
                        (currentNode.Parent as RedBlackTreeNode<T>).Left_Rotate();
                        w = currentNode.Parent.RightNode as RedBlackTreeNode<T>;
                    }
                    var wleft = w.LeftNode as RedBlackTreeNode<T>;
                    var wright = w.RightNode as RedBlackTreeNode<T> ;
                    if (wleft.Color == NodeColor.Black && wright.Color == NodeColor.Black)
                    {
                        w.Color = NodeColor.Red;
                        currentNode = currentNode.Parent as RedBlackTreeNode<T>;
                    }
                    else
                    {
                        if (wright.Color == NodeColor.Black)
                        {
                            wleft.Color = NodeColor.Black;
                            w.Color = NodeColor.Red;
                            w.Right_Rotate();
                            w = currentNode.Parent.RightNode as RedBlackTreeNode<T>;
                        }
                        else
                        {
                            w.Color = (w.Parent as RedBlackTreeNode<T>).Color;
                            (currentNode.Parent as RedBlackTreeNode<T>).Color = NodeColor.Black;
                            (w.RightNode as RedBlackTreeNode<T>).Color = NodeColor.Black;
                            w.Left_Rotate();
                            currentNode = currentNode.Tree.Root as RedBlackTreeNode<T>;
                        }
                    }
                }
                else //与上面的逻辑对称
                {
                    w = currentNode.Parent.RightNode as RedBlackTreeNode<T>;
                    if (w.Color == NodeColor.Red)
                    {
                        w.Color = NodeColor.Black;
                        (currentNode.Parent as RedBlackTreeNode<T>).Color = NodeColor.Red;
                        (currentNode.Parent as RedBlackTreeNode<T>).Right_Rotate();
                        w = currentNode.Parent.LeftNode as RedBlackTreeNode<T>;
                    }
                    var wleft = w.LeftNode as RedBlackTreeNode<T>;
                    var wright = w.RightNode as RedBlackTreeNode<T>;
                    if (wleft.Color == NodeColor.Black && wright.Color == NodeColor.Black)
                    {
                        w.Color = NodeColor.Red;
                        currentNode = currentNode.Parent as RedBlackTreeNode<T>;
                    }
                    else
                    {
                        if (wleft.Color == NodeColor.Black)
                        {
                            wright.Color = NodeColor.Black;
                            w.Color = NodeColor.Red;
                            w.Left_Rotate();
                            w = currentNode.Parent.LeftNode as RedBlackTreeNode<T>;
                        }
                        w.Color = (w.Parent as RedBlackTreeNode<T>).Color;
                        (currentNode.Parent as RedBlackTreeNode<T>).Color = NodeColor.Black;
                        (w.RightNode as RedBlackTreeNode<T>).Color = NodeColor.Black;
                        w.Right_Rotate();
                        currentNode = currentNode.Tree.Root as RedBlackTreeNode<T>;
                    }
                }
            }
            currentNode.Color = NodeColor.Black;
        }
    }

    public class RedBlackTreeNode<T> : TreeNode<T> where T : IComparable<T>
    {
        public NodeColor Color
        {
            get;
            set;
        }

        public bool IsBlack()
        {
            return Color == NodeColor.Black;
        }

        public bool IsRed()
        {
            return Color == NodeColor.Red;
        }

        public bool IsEmptyTreeNode
        {
            get
            {
                return null != this as EmptyTreeNode<T>;
            }
        }

        protected RedBlackTreeNode()
            : base(default(T))
        { }

        public RedBlackTreeNode(T data)
            : base(data)
        {
            this.LeftNode = EmptyTreeNode<T>.Instance();
            this.RightNode = EmptyTreeNode<T>.Instance();
            this.Parent = EmptyTreeNode<T>.Instance();
        }

        public RedBlackTreeNode(T data, NodeColor color)
            : base(data)
        {
            this.Color = color;
        }

        /// <summary>
        /// 左旋说明：左旋某个非空节点x，首先假设该节点的右孩子非空，然后让它的右孩子 y代替该节点的位置，该节点x连接到原右孩子y的左孩子上，
        /// y的左孩子成为x的右孩子。
        /// </summary>
        public virtual void Left_Rotate()
        {
            //判断该节点右树不为空
            Debug.Assert(null != this.RightNode);

            //将该节点下面的右节点的左子树，连接到该节点右孩子
            var rightNode = this.RightNode;
            this.RightNode = rightNode.LeftNode;
            if (EmptyTreeNode<T>.Instance() != rightNode.LeftNode)
            {
                rightNode.LeftNode.Parent = this;
            }

            //更新右孩子的父指针
            rightNode.Parent = this.Parent;

            //判断是否更新树根节点
            if (EmptyTreeNode<T>.Instance() == this.Parent)
            {
                this.Tree.Root = rightNode;
            }//判断该节点为父节点的左孩子还是右孩子，更新父节点的指针
            else
            {
                if (this == this.Parent.LeftNode)
                {
                    this.Parent.LeftNode = rightNode;
                }
                else
                {
                    this.Parent.RightNode = rightNode;
                }
                
            }

            //将该节点移到右孩子的左节点上
            rightNode.LeftNode = this;
            this.Parent = rightNode;

        }

        /// <summary>
        /// 右旋是上面左旋的叛过程
        /// </summary>
        public virtual void Right_Rotate()
        {
            //判断该节点右树不为空
            Debug.Assert(null != this.LeftNode);

            //将该节点下面的右节点的左子树，连接到该节点右孩子
            var leftNode = this.LeftNode;
            this.LeftNode = leftNode.RightNode;
            if (EmptyTreeNode<T>.Instance() != leftNode.RightNode)
            {
                leftNode.RightNode.Parent = this;
            }

            //更新右孩子的父指针
            leftNode.Parent = this.Parent;

            //判断是否更新树根节点
            if (EmptyTreeNode<T>.Instance() == this.Parent)
            {
                this.Tree.Root = leftNode;
            }//判断该节点为父节点的左孩子还是右孩子，更新父节点的指针
            else
            {
                if (this == this.Parent.LeftNode)
                {
                    this.Parent.LeftNode = leftNode;
                }
                else
                {
                    this.Parent.RightNode = leftNode;
                }

            }

            //将该节点移到右孩子的左节点上
            leftNode.RightNode = this;
            this.Parent = leftNode;
        }

        public RedBlackTreeNode<T> GetSuccessor()
        {
            if (EmptyTreeNode<T>.Instance() != this.RightNode)
            {
                return (this.RightNode as RedBlackTreeNode<T>).MinNode();
            }
            var parent = this.Parent as RedBlackTreeNode<T>;
            var tmp = this;
            while (this == parent.RightNode)
            {
                tmp = parent;
                parent = parent.Parent as RedBlackTreeNode<T>;
            }

            return parent;
        }

        public RedBlackTreeNode<T> MinNode()
        {
            var tmp = this;
            while (EmptyTreeNode<T>.Instance() != tmp.LeftNode)
            {
                tmp = tmp.LeftNode as RedBlackTreeNode<T>;
            }
            return tmp;
        }

        public RedBlackTreeNode<T> MaxNode()
        {
            var tmp = this;
            while (EmptyTreeNode<T>.Instance() != tmp.RightNode)
            {
                tmp = tmp.RightNode as RedBlackTreeNode<T>;
            }
            return tmp;
        }
    }

    /// <summary>
    /// 哨兵
    /// </summary>
    /// <typeparam name="T"></typeparam>
    public class EmptyTreeNode<T> : RedBlackTreeNodeExtend<T> where T : IComparable<T>
    {
        private static EmptyTreeNode<T> _instance;
        public static EmptyTreeNode<T> Instance()
        {
            if (null == _instance)
            {
                _instance = new EmptyTreeNode<T>();
            }
            return _instance;
        }
        public EmptyTreeNode()
        {
            this.Color = NodeColor.Black;
            this.Size = 0;
        }
    }

    public enum NodeColor
    {
        Red,
        Black
    }
}
